Search results for "binary [black hole]"
showing 10 items of 170 documents
A subquadratic algorithm for minimum palindromic factorization
2014
We give an $\mathcal{O}(n \log n)$-time, $\mathcal{O}(n)$-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string $S [1..n]$, in $\mathcal{O}(n \log n)$ time our algorithm returns the minimum number of palindromes $S_1,\ldots, S_\ell$ such that $S = S_1 \cdots S_\ell$. We also show that the time complexity is $\mathcal{O}(n)$ on average and $\Omega(n\log n)$ in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.
Finite state verifiers with constant randomness
2014
We give a new characterization of $\mathsf{NL}$ as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers. A corollary of our main result is that the class of outcome problems corresponding to O(log n)-space …
Quantum, stochastic, and pseudo stochastic languages with few states
2014
Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all th…
Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
2020
A prefix normal word is a binary word with the property that no substring has more $1$s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length $n$ as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in $\Oh(\log^2 n)$ amortized time per word, while the best generation algorithm hitherto has $\Oh(n)$ running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages.
On prefix normal words and prefix normal forms
2016
A $1$-prefix normal word is a binary word with the property that no factor has more $1$s than the prefix of the same length; a $0$-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of $1$s and $0$s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contai…
Intelligent Cloud Storage Management for Layered Tiers
2018
Today, the cloud offers a large array of possibilities for storage, with this flexibility comes also complexity. This complexity stems from the variety of storage mediums, such as, blob storage or NoSQL tables, and also from the different cost tiers within these systems. A strategic thinking to navigate this complex cloud storage landscape is important, not only for cost saving but also for prioritizing information, this prioritization has wider implications in other domains such as the Big Data realm, especially for governance and efficiency. In this paper we propose a strategy centered around probabilistic graphical model (PGM), this heuristic oriented management and organizational strate…
Split Bregman Method for Gravitational Wave Denoising
2014
This paper presents a progress report in our aim to develop a Total Variation algorithm for denoising of gravitational waves. These algorithms, are routinely employed in the context of image processing and they do not need any a priori information on the signals. We apply our method to two different types of numerically-simulated gravitational wave signals, namely burst produced from the core collapse of rotating stars and waveforms from binary black hole mergers, and present a preliminary assessment of its capabilities.
Global Coastal Permeability database (GCPdb)
2023
The Global Coastal Permeability Database contains both the input and output data of the Global Coastal Permeability Model developed by Tschaikowski et al. (2023) and available at DOI: 10.5281/zenodo.7845568. The model is implemented in R and calculates the coastal permeability for each shoreline segment of the global shoreline vector created by Sayre et al. (2019) with a 30-meter resolution and covering a spatial extent of 180.0°W to 180.0°E longitude and 60.8°S to 83.7°N latitude. The coastline is separated into three sections (A: coastal aquifer section, B: shoreline section, C: shallow section), and permeability values and ranges are provided for each section. Permeability values were de…
Au n+-induced decomposition of N2O
1994
Reactions between small gold cluster ions, Au, and N2O were studied in a Penning trap mass spectrometer. Gold clusters were produced by laser vaporization and injected into a Penning trap. After reaction times of 50–7000ms the products were detected by time-of-flight mass spectrometry. For the major reaction channel, Au + N2OAu1,2N + NO+, rates of (0.9±0.1)×10−12 cm3 s−1 and (2.4±0.4)×10−12 cm3 s−1 were determined which are about a factor 500 below the collision rate. The corresponding activation energies for N2O decomposition were estimated to lie below 0.6 eV and 0.3 eV. Additional products with small branching ratios were detected, viz. the ions Au1O+, Au1N2O+, Au2N+, Au2NO+, Au2N2O+, Au…
A Gravitational-wave Measurement of the Hubble Constant Following the Second Observing Run of Advanced LIGO and Virgo
2021
This paper presents the gravitational-wave measurement of the Hubble constant (H 0) using the detections from the first and second observing runs of the Advanced LIGO and Virgo detector network. The presence of the transient electromagnetic counterpart of the binary neutron star GW170817 led to the first standard-siren measurement of H 0. Here we additionally use binary black hole detections in conjunction with galaxy catalogs and report a joint measurement. Our updated measurement is H 0 = km s-1 Mpc-1 (68.3% of the highest density posterior interval with a flat-in-log prior) which is an improvement by a factor of 1.04 (about 4%) over the GW170817-only value of km s-1 Mpc-1. A significant …